package com.company;

import java.util.*;

public class Using {


    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 冒泡排序
     * 注意内层遍历 -i，比较内层前后元素，并做交换
     * @param letters
     */
    public static void sortByMaoPao(List<Character> letters) {
        for (int i = 0; i < letters.size(); i++) {
            for (int j = 0; j < letters.size()-1-i; j++) {
                if((letters.get(j)).toString().toLowerCase().toCharArray()[0]
                        > (letters.get(j+1)).toString().toLowerCase().toCharArray()[0]){
                    char temp = letters.get(j);
                    letters.set(j, letters.get(j+1));
                    letters.set(j+1, temp);
                }
            }
        }
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 合唱队 需要出列 (N-k) 人则剩下的组成左右最长子序列
     * A1<A2..<Ai>Ai>Ai+1>Ak
     * @param args
     */
    public static void QueneHeChangDui(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int total = sc.nextInt();
            //最少等于总数减去最大队形数
            //最大队形数等于左侧最大+右侧最大+1
            //动态规划int[i]计算第i时左侧最大队形数和右侧最大队形数
            int[] height = new int[total];
            int[] lmax = new int[total];
            int[] rmax = new int[total];
            for (int i = 0; i < total; i++) {
                height[i] = sc.nextInt();
                lmax[i] = 1;
                rmax[i] = 1;
            }
            TreeMap<Integer, Vector<Integer>> left = null;
            doArrayLeftASC(height, lmax, left);
            TreeMap<Integer, Vector<Integer>> right = null;
            doArrayRightDESC(height, rmax, right);

            int end = 0;
            for (int i = 0; i < total; i++) {
                end = Math.max(end, lmax[i]+rmax[i]-1);
            }
            //System.out.println(Arrays.toString(lmax));
            //System.out.println(Arrays.toString(rmax));
            System.out.println(total-end);
        }
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 逆向递增最长子序列
     * 12 7 19 20 24 70 64 45 68 29 13 88
     * @param quene
     * @param rmax
     * @param childs
     */
    public static void doArrayRightDESC(int[] quene, int[] rmax, TreeMap<Integer, Vector<Integer>> childs) {
        int total = quene.length;
        if(null == childs){
            childs = new TreeMap<Integer, Vector<Integer>>();
        }
        for (int i = total -1; i>=0; i--){
            //子序列初始化
            if(!childs.containsKey(i)){
                if(null == childs.get(i)){
                    childs.put(i, new Vector<>());
                }
            }
            for(int r = total -1; r > i; r--){
                //子序列判断取值核心
                if(quene[i] > quene[r] && rmax[r]+1 > rmax[i]){
                    rmax[i] = rmax[r]+1;
                    //子序列缓存
                    childs.get(i).add(quene[r]);
                }
            }
            childs.get(i).add(quene[i]);
        }
        //System.out.println(childs);
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 正向递增最长子序列
     * 12 7 19 20 24 70 64 45 68 29 13 88
     * @param quene
     * @param lmax
     * @param childs
     */
    public static void doArrayLeftASC(int[] quene, int[] lmax, TreeMap<Integer, Vector<Integer>> childs) {
        int total = quene.length;
        if(null == childs){
            childs = new TreeMap<Integer, Vector<Integer>>();
        }
        for (int i = 0; i < total; ++i) {
            //子序列初始化
            if(!childs.containsKey(i)){
                if(null == childs.get(i)){
                    childs.put(i, new Vector<>());
                }
            }
            for (int l = 0; l < i; ++l) {
                //子序列最长判断取值核心
                if(quene[l] < quene[i] && lmax[l]+1 > lmax[i]){
                    lmax[i] = lmax[l]+1;
                    //子序列缓存
                    childs.get(i).add(quene[l]);
                }
            }
            childs.get(i).add(quene[i]);
        }
        //System.out.println(childs);
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 汽水 喝3返1，最后借1喝3还1 喝多少
     * @param num
     * @return
     */
    private static int caculQiShui(int num) {
        int end = 0;
        if(num != 0){
            if(num >= 10){
                end = ((int) num /10) * 5;
                if(num %10 != 0){
                    end += doLast(num %10);
                }
            }else{
                end += doLast(num);
            }
        }
        return end;
    }

    private static int doLast(int last) {
        int end = 0;
        while (last-3 >= 0){
            end ++;
            last = last - 3;
            last++;
        }
        if(last == 2){
            end++;
        }
        return end;
    }

    /***
     * 密码合法性验证
     * @param args
     */
    public static void vallidPsd(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            String line = sc.nextLine();
            boolean valid1 = true;
            boolean valid2 = true;
            boolean valid3 = true;
            if(line.length() <= 8){
                valid1 = false;
            }
            int az = 0, azb = 0, num = 0, other = 0;
            for (Character c : line.toCharArray()) {
                boolean oth = true;
                if('a' <= c && 'z' >= c){
                    az = az==0 ? az+1:az;
                    oth = false;
                }
                if('A' <= c && 'Z' >= c){
                    azb = azb==0 ? azb+1:azb;
                    oth = false;
                }
                if(hasNum(c)){
                    num = num==0 ? num+1:num;
                    oth = false;
                }
                if(oth){
                    other = other==0 ? other+1:other;
                }
            }
            if(az+azb+num+other < 3){
                valid2 = false;
            }
            Map<String, Integer> repeatMap = repeatStr(line, null);
            for (Map.Entry<String, Integer> repeat : repeatMap.entrySet()) {
                if(repeat.getKey().length() > 2){
                    valid3 = false;
                    break;
                }
            }
            if(!valid1 || !valid2 || !valid3){
                System.out.println("NG");
            }else{
                System.out.println("OK");
            }
        }
        sc.close();
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 直接查询字符串中所有字符对应的个数
     * @param line
     * @return
     */
    public static Map<String, Integer> repeatChar(String line){
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < line.length() - 1; i++) {
            String left = line.substring(i, i+1);
            String right = line.substring(i+1);
            int repeat = 1;
            while (right.contains(left)){
                repeat++;
                right = right.substring(right.indexOf(left)+1);
            }
            if(!map.containsKey(left)){
                map.put(left, repeat);
            }
        }
        return map;
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 查找字符串中所有重复子串及数量
     * 子串大于等于2个字符
     * 单字符重复
     * 例 abcdefghcdefaecdehkcdefdedehkcfa
     * @param line
     * @param len  null 则查询所有子串，否则查询指定字符长【1 单字符重复， 2 两个字符重复】的重复子串或字符数
     * @return
     */
    public static Map<String, Integer> repeatStr(String line, Integer len){
        Map<String, Integer> map = new HashMap<>();
        Boolean doChildStr = false;
        if(null == len){
            len = 2;
            doChildStr = true;
        }
        for (int i = 0; i < line.length()-len; i++) {
            //开始相邻2字符
            int f = i;
            String left = line.substring(i, i + len);
            String right = line.substring(i + len);
            while (right.contains(left)){
                int repeat = 1;//自己本身加 1
                String temp = right;
                while (temp.contains(left)){
                    repeat++; //重复加 1
                    temp = temp.substring(temp.indexOf(left)+left.length());
                }
                //记录重复数(包括自己)
                if(!map.containsKey(left)){
                    map.put(left, repeat);
                }
                if(!doChildStr){
                    //单个重复字符,右侧匹配结束重置right空，循环会跳出
                    right = "";
                }else{
                    //子串重复，即重复子串大于等于2，
                    //++f 先运算后赋值  f++; 先赋值后运算
                    f = ++f;
                    left = line.substring(i, f+1);
                    right = line.substring(f+1);
                }
            }
        }
        return map;
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 字符是数字
     * @param num
     * @return
     */
    public static boolean hasNum(Character num){
        Integer[] nums = new Integer[]{0,1,2,3,4,5,6,7,8,9};
        for (Integer c:nums) {
            if(c.toString().equals((num.toString()))){
                return true;
            }
        }
        return false;
    }

    /**
     * 错误日志 有序Map 组装查询
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        while(sc.hasNextLine()){
            String line = sc.nextLine();
            String[] error = line.split(" ");
            String filePath = error[0];
            String fileName = filePath.substring(filePath.lastIndexOf("\\")+1, filePath.length());
            if(fileName.length() > 16){
                fileName = fileName.substring(fileName.length()-16, fileName.length());
            }
            String key = fileName.concat("-").concat(error[1]);
            if(map.containsKey(key)){
                map.put(key, map.get(key)+1);
            }else{
                map.put(key, 1);
            }
        }
        //遍历结束输出
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        if(entries.size() > 8){
            int from = 0;
            for (Map.Entry<String, Integer> entry : entries) {
                if(from >= entries.size() - 8){
                    String[] key = entry.getKey().split("-");
                    System.out.println(key[0] + " " + key[1] + " " + entry.getValue());
                }
                from++;
            }
        }else{
            for (Map.Entry<String, Integer> entry : entries) {
                String[] key = entry.getKey().split("-");
                System.out.println(key[0] + " " + key[1] + " " + entry.getValue());
            }
        }
        sc.close();
    }

    /**
     * 合法掩码IP判断
     * @param args
     */
    public static void IP(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<String> nums = new ArrayList<>();
        int a=0,b=0,c=0,d=0,e=0,x=0,s=0;
        for (int i = 0; i < 256; i++) {
            nums.add(String.valueOf(i));
        }
        while(sc.hasNextLine()){
            String line = sc.nextLine();
            String[] ipym = line.split("[~]");
            String ip = ipym[0];
            if(validIPYM(ipym[1], true, nums)){
                if(validIPYM(ip, false, nums)){
                    Integer ip1 = Integer.parseInt(ip.split("[.]")[0]);
                    Integer ip2 = Integer.parseInt(ip.split("[.]")[1]);
                    if(ip1 >= 1 && ip1 <= 126){
                        a++;
                    }
                    if(ip1 >= 128 && ip1 <= 191){
                        b++;
                    }
                    if(ip1 >= 192 && ip1 <= 223){
                        c++;
                    }
                    if(ip1 >= 224 && ip1 <= 239){
                        d++;
                    }
                    if(ip1 >= 240 && ip1 <= 255){
                        e++;
                    }
                    if(ip1 == 10
                            || (ip1 == 172 && (ip2 >= 16 && ip2 <= 31))
                            || (ip1 == 192 && ip2 == 168)){
                        s++;
                    }
                }else{
                    x++;
                }
            }else{
                x++;
            }
        }
        System.out.println(""+a+" "+b+" "+c+" "+d+" "+e+" "+x+" "+s);
        sc.close();
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * String b = Integer.toBinaryString(Integer.parseInt(num));
     * 数字转二进制，高位需要补0，达到二进制8位
     * @param ipym
     * @param isym
     * @param nums
     * @return
     */
    public static boolean validIPYM(String ipym, boolean isym, List<String> nums){
        boolean isValid = false;
        String[] all = ipym.split("[.]");
        List<String> yms = new ArrayList<>();
        if(all.length == 4){
            isValid = true;
            for (int i = 0; i < all.length; i++) {
                String num = all[i];
                if(nums.contains(num)){
                    if(isym){
                        String b = Integer.toBinaryString(Integer.parseInt(num));
                        if(b.length() < 8){
                            String bb = "";
                            for(int o = 0; o < 8 - b.length();o++){
                                bb = bb.concat("0");
                            }
                            //前面拼接0  千万注意
                            b = bb.concat(b);
                        }
                        yms.add(b);
                    }else{
                        isValid = isValid && true;
                    }
                }else{
                    isValid = false;
                }
            }
        }else{
            isValid = false;
        }
        if(isym){
            String bym = "";
            for (String ym : yms) {
                bym = bym.concat(ym);
            }
            if(bym.contains("1") && bym.contains("0")
                    && bym.lastIndexOf("1")== (bym.indexOf("0")-1)){
                isValid = true && isValid;
            }else{
                isValid = false;
            }
        }
        return isValid;
    }

    static class Good{
        public int price;
        public int weight;
        public int parentIndex;

        public Good(int price, int weight, int parentIndex) {
            this.price = price;
            this.weight = weight;
            this.parentIndex = parentIndex;
        }
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 购物单 买指定钱数的主附件的权重加和最大【动态规划】
     * 用j钱买一组主附件依次扣获取最大weight  pw[j] 用上一次的最大值和新情况的值 取最大，不断复用上一次的结果和当前的结果比较，取最大
     * @param args
     */
    public static void money(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int money = sc.nextInt();
            //价格均为10倍数，整除可以少遍历
            money/=10;
            int num = sc.nextInt();
            Good[] goods = new Good[num];
            Map<Good, List<Good>> masters = new HashMap<>();
            for (int i = 0; i < num; i++) {
                int price = sc.nextInt();
                int weight = sc.nextInt()*price;
                //价格均为10倍数，整除可以少遍历，和总钱数匹配，也除以10
                price/=10;
                int parentIndex = sc.nextInt();
                goods[i] = new Good(price, weight, parentIndex);
                if(goods[i].parentIndex == 0){
                    masters.put(goods[i], new ArrayList<>());
                }
            }

            for (int i = 0; i < goods.length; i++) {
                if(goods[i].parentIndex != 0){
                    masters.get(goods[goods[i].parentIndex-1]).add(goods[i]);
                }
            }
            //money+1 为了满足遍历钱数到最后是money,否则数据会溢出，找不到下表为money的数据
            int[] pw= new int[money+1];
            for (Good m:masters.keySet()) {
                for (int j = money; j >= 1; j--) {
                    if(m.price <= j){
                        //用j钱买一组主附件依次扣获取最大weight  pw[j] 用上一次的最大值和新情况的值 取最大，不断复用上一次的结果和当前的结果比较，取最大
                        pw[j] = Math.max(pw[j], pw[j-m.price]+m.weight);
                        List<Good> childs = masters.get(m);
                        for (Good child:childs) {
                            if(child.price + m.price <= j){
                                pw[j] = Math.max(pw[j], pw[j-child.price-m.price]+m.weight+child.weight);
                            }
                        }
                        if(childs.size() == 2){
                            Good c1 = childs.get(0);
                            Good c2 = childs.get(1);
                            if(m.price+c1.price+c2.price <= j){
                                pw[j] = Math.max(pw[j], pw[j-m.price-c1.price-c2.price]+m.weight+c1.weight+c2.weight);
                            }
                        }
                    }
                }
            }
            System.out.println(pw[money]);
        }

    }

    /**
     * Integer 二进制后1或0的个数
     * @param args
     */
    public static void binaryIn1Or0(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            Integer line = in.nextInt();
            char[] chars = Integer.toBinaryString(line).toCharArray();
            int total = 0;
            for (int i = 0; i < chars.length; i++) {
                if(chars[i] == '1'){
                    total++;
                }
            }
            System.out.println(total);
        }
    }


    /**
     * 小数点大于等于5向上取整，反之向下
     * @param num
     */
    public static void flot(Float num){
        if(num - num.longValue() >= 0.5 ){
            System.out.println(num);
        }else{
            System.out.println(num.longValue());
        }
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * Math.sqrt 平方根值
     * 质数因子计算
     * @param num
     */
    public static void mod(Long num){
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0){
                System.out.print(i+" ");
                num = num/i;
                i--;
            }
        }
        System.out.println(num+" ");
    }

    /**
     * •连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；
     * •长度不是8整数倍的字符串请在后面补数字0，空字符串不处理
     *  输出到长度为8的新字符串数组
     * @param args
     */
    public static void splitArrays(String[] args) {
        int len = 8;
        String rix = "0";
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String line = in.nextLine();
            int has = line.length() % len;
            if(has != 0){
                int rn = len - has;
                while(rn > 0){
                    rn--;
                    line = line.concat(rix);
                }
            }
            int rstn = line.length() / len;
            String[] arrays = new String[0 == rstn? 1:rstn];
            for (int i = 0; i < rstn; i++) {
                arrays[i] = line.substring(i*len, (i+1)*len);
                System.out.println(arrays[i]);
            }
        }
    }

    /**
     * 排序&去重--明明的随机数-java实现
     * @param args
     */
    public static void randomArrays(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] data = new int[n];
            for (int i = 0; i < n; i++) {
                data[i] = scanner.nextInt();
            }
            sort(data, 0, data.length-1);
            data = reDel(data);
            for (int i = 0; i < data.length; i++) {
                System.out.println(data[i]);
            }
        }
    }
    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 数组去重
     * @param array
     * @return
     */
    public static int[] reDel(int[] array){
        int[] news = new int[0];
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            if(i == 0 || array[i] != array[i-1]){
                int[] mores = new int[news.length+1];
                for (int j = 0; j < news.length; j++) {
                    mores[j] = news[j];
                }
                news = mores;
                news[sum] = array[i];
                sum++;
            }
        }
        return news;
    }

    /**
     * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     * 快速排序
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static void sort(int[] array, int start, int end){
        if(start > end){
            return;
        }
        int left = start;
        int right = end;
        int base = array[left];
        while (left < right){
            while (array[right] >= base && left < right){
                right--;
            }
            array[left] = array[right];
            while (array[left] <= base && left < right){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = base;
        int index = left;
        sort(array, start, index-1);
        sort(array, index+1, end);
    }
    public static Map<String, String> numCharMap = new HashMap<>();
    public static String numStr = "0123456789";
    static {
        numCharMap.put("1","1");
        numCharMap.put("abc","2");
        numCharMap.put("def","3");
        numCharMap.put("ghi","4");
        numCharMap.put("jkl","5");
        numCharMap.put("mno","6");
        numCharMap.put("pqrs","7");
        numCharMap.put("tuv","8");
        numCharMap.put("wxyz","9");
        numCharMap.put("0","0");
    }
    /**
     * 密码解密
     * @param line
     * @param end
     */
    private static void passwordTo(String line, String end) {
        //A 65 a 97
        for (int i = 0; i< line.length(); i++) {
            char c = line.charAt(i);
            if('A' <= c && c <= 'Z'){
                c = (char) (c + 32);
                if(c == 'z'){
                    c = 'a';
                }else{
                    c = (char) (c + 1);
                }
                end += c;
            }else if('a' <= c && c<= 'z'){
                for (String key : numCharMap.keySet()) {
                    if(key.contains(""+c)){
                        end += numCharMap.get(key);
                    }
                }
            }else{
                end += c;
            }
        }
        System.out.println(end);
    }
}
